<?php
/**
 * @title 146. LRU缓存机制 - 哈希+队列
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class LRUCache {
    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->maxLength = $capacity;
        $this->init = 0;
        $this->hashs = [];
        $this->list = [];
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        $result = -1;

        /**
         * @since 2020-08-17 哈希是否存在
         */
        if(isset($this->hashs[$key])){
            list($listKey, $result) = $this->hashs[$key];

            /**
             * @since 2020-08-17 清理list, 入list队尾
             */
            unset($this->list[$listKey]);
            $this->list[$this->init] = $key;

            /**
             * @since 2020-08-17 更新哈希的listKey
             */
            $this->hashs[$key][0] = $this->init;

            $this->init++;
        } else {}

        /**
         * @return
         */
        return $result;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        /**
         * @since 2020-08-17 哈希是否存在
         */
        if(isset($this->hashs[$key])){
            /**
             * @since 2020-08-17 数组只有1个, 更新value
             */
            if(count($this->list) == 1){
                $this->hashs[$key][1] = $value;
            } else {
                $listKey = $this->hashs[$key][0];

                /**
                 * @since 2020-08-17 list删除, 新增
                 */
                unset($this->list[$listKey]);
                $this->list[$this->init] = $key;

                /**
                 * @since 2020-08-17 更新hash
                 */
                $this->hashs[$key] = [$this->init, $value];

                $this->init++;
            }
        } elseif(count($this->list) < $this->maxLength){
            /**
             * @since 2020-08-17 长度足够, 新增
             */
            $this->list[$this->init] = $key;
            $this->hashs[$key] = [$this->init, $value];
            $this->init++;
        } else {
            /**
             * @since 2020-08-17 先移除list一个, 删除hash对应
             */
            $delListKey = key($this->list);
            unset($this->hashs[$this->list[$delListKey]]);
            unset($this->list[$delListKey]);

            /**
             * @since 2020-08-17 新增
             */
            $this->list[$this->init] = $key;
            $this->hashs[$key] = [$this->init, $value];
            $this->init++;
        }
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.17_2.php
 */
$datas = [
    // [
    //     ["LRUCache", "put","put","get","put","get","put","get","get","get"],
    //     [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],
    // ],
    [
        ["LRUCache","put","put","put","put","get","get"],
        [[2],[2,1],[1,1],[2,3],[4,1],[1],[2]],
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    $obj = new LRUCache($data[1][0][0]);
    echo "LRUCache(", $data[1][0][0] ,")", PHP_EOL;

    for ($i=1; $i<count($data[0]); $i++){
        if($data[0][$i] == "get"){
            echo "get(", $data[1][$i][0] ,") = ";
            echo $obj->$data[0][$i]($data[1][$i][0]), PHP_EOL;
        } else {
            echo "put(", implode(",", $data[1][$i]) ,") = NULL", PHP_EOL;
            $obj->$data[0][$i](...$data[1][$i]);
        }
    }

    echo str_repeat(PHP_EOL, 3);
}
$xhprof->end();
